package leetCode.q236;

public class Q236 {
    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(){}
        TreeNode(int val){
            this.val = val;
        }
        public TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    private TreeNode ans = null;

    /**
     * 返回结果表示根包不包含pq
     * ans才携带最终返回信息
     */
    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
//        根是空，肯定不包含
        if (root == null) return false;

        //左右子树包不包含
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        //如果左右子树都包含，或者一个是根节点，一个在子树那么root就是返回结果
        if ((lson && rson)
                || ((root.val == p.val || root.val == q.val)
                        && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor0(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }


}
